package 第7周_二分查找法.二分查找法;

public class BinarySearch {

    private BinarySearch(){}

    /**
     * 二分查找法 （递归实现）
     * @param data 用户想要查找的数组
     * @param target 用户想要查找的目标
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int search(E[] data, E target){
        int l = 0, r = data.length - 1;

        //在data[l, r]中查找 target
        while (l <= r){
            int mid = l + (r - l) / 2;

            if (data[mid].compareTo(target) == 0){
                return mid;
            }
            if (data[mid].compareTo(target) < 0){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找法 （递归实现）
     * @param data 用户想要查找的数组
     * @param target 用户想要查找的目标
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int searchR(E[] data, E target){
        return searchR(data, 0, data.length - 1, target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target){

        if(l > r){
            return -1;
        }

        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0){
            return mid;
        }
        if (data[mid].compareTo(target) < 0){
            return searchR(data, mid + 1, r, target);
        }
        return searchR(data, 0, mid - 1, target);
    }
}
